翻訳と辞書 Words near each other ・ Rainbow Range (Rocky Mountains) ・ Rainbow Records ・ Rainbow Reef ・ Rainbow Cheetah ・ Rainbow Christians ・ Rainbow cichlid ・ Rainbow City ・ Rainbow City (TV series) ・ Rainbow City, Alabama ・ Rainbow City, Panama ・ Rainbow Coalition ・ Rainbow Coalition (Fred Hampton) ・ Rainbow Coffee House ・ Rainbow Collective ・ Rainbow College, Lagos-Ibadan Exp. way, Maba ・ Rainbow coloring ・ Rainbow Computing ・ Rainbow Connection ・ Rainbow Connection (album) ・ Rainbow cookie ・ Rainbow Country ・ Rainbow Court ・ Rainbow Crafts ・ Rainbow crow ・ Rainbow cup ・ Rainbow cusk eel ・ Rainbow Dam ・ Rainbow Dance ・ Rainbow darter ・ Rainbow discography Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Rainbow coloring ： ウィキペディア英語版 Rainbow coloring In graph theory, a path in an edge-colored graph is said to be rainbow if no color repeats on it. A graph is said to be rainbow colored if there is a rainbow path between each pair of its vertices. If there is a rainbow shortest path between each pair of vertices, the graph is said to be strong rainbow colored. == Definitions and bounds == The rainbow connection number of a graph $G$ is the minimum number of colors needed to rainbow color $G$, and is denoted by $\backslash text(G)$. Similarly, the strong rainbow connection number of a graph $G$ is the minimum number of colors needed to strong rainbow color $G$, and is denoted by $\backslash text(G)$. Clearly, each strong rainbow coloring is also a rainbow coloring, while the converse is not true in general. It is easy to observe that to rainbow color any connected graph $G$, we need at least $\backslash text(G)$ colors, where $\backslash text(G)$ is the diameter of $G$ (i.e. the length of the longest shortest path). On the other hand, we can never use more than $m$ colors, where $m$ denotes the number of edges in $G$. Finally, because each strong rainbow colored graph is rainbow colored, we have that $\backslash text(G)\; \backslash leq\; \backslash text(G)\; \backslash leq\; \backslash text(G)\; \backslash leq\; m$. The following are the extremal cases: *$\backslash text(G)\; =\; \backslash text(G)\; =\; 1$ if and only if $G$ is a complete graph. *$\backslash text(G)\; =\; \backslash text(G)\; =\; m$ if and only if $G$ is a tree. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Rainbow coloring」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.